// 搜索二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
public class LowestCommonAncestorBinarySearch {
      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q){
                  return root;
            }
            if( (p.val < root.val && q.val > root.val ) || (p.val > root.val && q.val < root.val ) ) {
                  return root;
            }

            if(p.val < root.val  && q.val < root.val){
                  return lowestCommonAncestor(root.left,p,q);
            }else{
                  return lowestCommonAncestor(root.right,p,q);
            }
      }
}
